package algo.utilitaire;

import algo.graphe.Noeud;

/**
 *
 * @author <a href="mailto:christian.dramsy@gmail.com>DRAMSY Christian</a>
 */
public class UtilitaireTas {

    /**
     * retourne l'indice de père de i;
     * @param i
     * @return
     */
    private static int getIndicePere(int i) {
        //   si i est pair
        int retour = (int) ((i + 1) / 2) - 1;
        return (retour < 0 ? 0 : retour);
    }

    /**
     * Retourne l'indice du fils gauche de i
     * @param i
     * @return
     */
    private static int getIndiceFilsGauche(int i) {
        return ((i + 1) * 2 - 1);
    }

    /**
     * Retourne l'indice du fils droit de i
     * @param i
     * @return
     */
    private static int getIndiceFilsDroit(int i) {
        return ((i + 1) * 2);
    }

    /**
     * Ajoute un noeud dans un tas
     * Pour cet algorithme, on peut éfféctuer h echanges au maximum. h etant la hauteur de l'arbre
     * @param tas
     * @param v
     * @return le nouveau tas
     */
    public static Noeud[] ajouter(Noeud[] tas, Noeud v) {
        /**
         * A savoir :
         *  -   Pour tout i de 2 à n(nombre de noeud de l'arbre)
         *      -   père de Tas[i] est Tas[partieEntiere(i/2)]
         *  -   Pour tout i de 1 à partieEntière(n/2)
         *      -   fils gauche de Tas[i] est Tas[2i]
         *      -   fils droit de Tas[i] est Tas[2i+1]
         */
        Noeud[] newTas = new Noeud[tas.length + 1];
        //  si l'arbre etait vide
        if (tas.length == 0) {
            newTas[0] = v;
        } else {
            //  Copie de tas dans newTas
            System.arraycopy(tas, 0, newTas, 0, tas.length);

            //  placement de v sur la dernière feuille libre de l'arbre(dernière case du tableau)
            int indiceV = tas.length;
            newTas[indiceV] = v;
            //  récuperation du père de v
            int indicePereV = UtilitaireTas.getIndicePere(indiceV);
            Noeud pereV = newTas[indicePereV];

            while (v.getValeur() <= pereV.getValeur()) {
                //System.out.println(indicePereV + ":" + indiceV);
                if (indicePereV != indiceV) {

                    //  Echange de v et pereV dans l'arbre
                    //  -   Echange de valeur
                    Noeud tmp = new Noeud(newTas[indiceV].getNum(), newTas[indiceV].getValeur());

                    newTas[indiceV].setValeur(newTas[indicePereV].getValeur());
                    newTas[indiceV].setNum(newTas[indicePereV].getNum());

                    newTas[indicePereV].setValeur(tmp.getValeur());
                    newTas[indicePereV].setNum(tmp.getNum());
                    //  -   Echange d'indice
                    indiceV = indicePereV;

                    indicePereV = UtilitaireTas.getIndicePere(indiceV);
                    pereV = newTas[indicePereV];
                } else {
                    break;
                }
            }
        }
        return newTas;
    }

    /**
     * Retourne le nouveau Tas et met la valeur de la racine ans valeurArecuperer
     * Pour cet algorithme on peut effectuer h echanges au maximum , h etant la taille de l'ecran
     * @param Tas
     * @return
     */
    public static Noeud[] suppressionRacine(Noeud[] Tas) {
        if (Tas.length > 0) {
            int indiceRacine = 0;
            int indiceMinimum;
            int indiceFilsGauche;
            int indiceFilsDroit;

            //  Le nouveau tas sera un tas avec une valeure en moin, donc la taille diminue
            if (Tas.length == 1) {
                return new Noeud[0];
            }

            
            //  Remplacement de la valeur de la racine par la valeur de la dernière feuille du tas de depart
            Tas[indiceRacine] = Tas[Tas.length - 1];

            indiceFilsDroit = UtilitaireTas.getIndiceFilsDroit(indiceRacine);
            indiceFilsGauche = UtilitaireTas.getIndiceFilsGauche(indiceRacine);
            
            //  S'il n'a pas de fils droit(Donc il n'a qu'un fils gauche)
            if (indiceFilsDroit >= Tas.length) {
                indiceMinimum = indiceFilsGauche;
            } else {
                indiceMinimum = Tas[indiceFilsDroit].getValeur() > Tas[indiceFilsGauche].getValeur() ? indiceFilsGauche : indiceFilsDroit;
            }


            while (Tas[indiceRacine].getValeur() > Tas[indiceMinimum].getValeur()) {
                Noeud tmp = new Noeud(Tas[indiceRacine].getNum(), Tas[indiceRacine].getValeur());

                Tas[indiceRacine].setValeur(Tas[indiceMinimum].getValeur());
                Tas[indiceRacine].setNum(Tas[indiceMinimum].getNum());

                Tas[indiceMinimum].setValeur(tmp.getValeur());
                Tas[indiceMinimum].setNum(tmp.getNum());


                indiceRacine = indiceMinimum;

                indiceFilsDroit = UtilitaireTas.getIndiceFilsDroit(indiceRacine);
                indiceFilsGauche = UtilitaireTas.getIndiceFilsGauche(indiceRacine);

                //  la racine est une feuille
                if (indiceFilsGauche >= Tas.length) {
                    break;
                }
                //  S'il n'a pas de fils droit(Donc il n'a qu'un fils gauche)
                if (indiceFilsDroit >= Tas.length) {
                    indiceMinimum = indiceFilsGauche;
                } else {
                    indiceMinimum = Tas[indiceFilsDroit].getValeur() > Tas[indiceFilsGauche].getValeur() ? indiceFilsGauche : indiceFilsDroit;
                }
            }
            Noeud[] newTas = new Noeud[Tas.length - 1];
            //  copie de tas dans newTas(ATTENTION : la valeur de la dernière feuille es perdue)
            System.arraycopy(Tas, 0, newTas, 0, Tas.length - 1);
            return newTas;
        }
        //  S'il n'y a pas de valeur dans le tas on retourne juste moin_infini
        return null;
    }
}